package com.liu.algorithm.sort;

import java.util.Arrays;

/**
 * @author LiuZhiYong
 * @description 冒泡排序
 * @date 2022-10-21
 **/
public class Code2BubbleSort {

    /**
     * 冒泡排序
     *
     * @param arr   待排序数组
     * 长度为n的数组 需要做n-1轮排序
     * 每轮 由第一个数开始,依次和相邻的数比较,把较大的数后移, 下一轮比较的次数-1
     * 比较次数:
     * 第1轮  比较n-1次
     * 第2轮  比较n-2次
     * 第3轮  比较n-3次
     * ...
     * 第n-1轮    比较1次
     * 等差数列求和 Sn = n * a1 + n(n-1)*d/2 = aN^2 + bN + c
     * 时间复杂度O(N^2)
     *
     * @author liuzhiyong
     * @date 2022/10/21
     */
    public static void buubleSort(int[] arr) {
        if (null == arr || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j+1]) {
                    swap(arr, j, j+1);
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }

    /**
     * i 和 j 位置上的元素调换位置
     *
     * @param arr 数组
     * @param i   下标i
     * @param j   下标j
     * @author liuzhiyong
     * @date 2022/10/18
     */
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = {5, 5, 4, 7, 4, 9, 4, 3, 2, 1};
        buubleSort(arr);
    }

}
